import java.util.Stack;

/**
 * @program: LeetCode
 * @description: LeetCode : 剑指 Offer II 028. 展平多级双向链表
 * @author: WXY
 * @create: 2022-12-26 11:05
 * @Version 1.0
 **/

public class offer_nine2_flatten {
    class Node {
        public int val;
        public Node prev;
        public Node next;
        public Node child;
    }

    public Node flatten(Node head) {
        Stack<Node> stack = new Stack<>();
        Node pre = null,cur = head;
        while (cur != null || !stack.isEmpty()) {
            if (cur == null) cur = stack.pop();
            if (cur.child != null) {
                if (cur.next != null) stack.push(cur.next);
                cur.next = cur.child;
                cur.child = null;
            }
            cur.prev = pre;
            if (pre != null)pre.next = cur;
            pre = cur;
            cur = cur.next;
        }
        return head;
    }
}
